Search for: All records

In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in TC². Our approach builds on the framework of Köbler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded treewidth. Here, we use the framework of Grohe & Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairs and flip functions. In order to control the depth of our circuit, we leverage the fact that any graph of rank-width k admits a rank decomposition of width ≤ 2k and height O(log n) (Courcelle & Kanté, WG 2007). This allows us to utilize an idea from Wagner (CSR 2011) of tracking the depth of the recursion in our computation. Furthermore, after splitting the graph into connected components, it is necessary to decide isomorphism of said components in TC¹. To this end, we extend the work of Grohe & Neuen (ibid.) to show that the (6k+3)-dimensional Weisfeiler-Leman (WL) algorithm can identify graphs of rank-width k using only O(log n) rounds. As a consequence, we obtain that graphs of bounded rank-width are identified by FO + C formulas with 6k+4 variables and quantifier depth O(log n). Prior to this paper, isomorphism testing for graphs of bounded rank-width was not known to be in NC. 

In this paper, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht-Fraisse bijective pebble game in Hella's (Ann. Pure Appl. Log., 1989) hierarchy. This is a Spoiler-Duplicator game in which Spoiler can place up to two pebbles each round. While it trivially solves graph isomorphism, it may be nontrivial for finite groups, and other ternary relational structures. We first provide a novel generalization of Weisfeiler-Leman (WL) coloring, which we call 2-ary WL. We then show that the 2-ary WL is equivalent to the second Ehrenfeucht-Fraisse bijective pebble game in Hella's hierarchy. Our main result is that, in the pebble game characterization, only O(1) pebbles and O(1) rounds are sufficient to identify all groups without Abelian normal subgroups (a class of groups for which isomorphism testing is known to be in P; Babai, Codenotti, & Qiao, ICALP 2012). In particular, we show that within the first few rounds, Spoiler can force Duplicator to select an isomorphism between two such groups at each subsequent round. By Hella's results (ibid.), this is equivalent to saying that these groups are identified by formulas in first-order logic with generalized 2-ary quantifiers, using only O(1) variables and O(1) quantifier depth. 

Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming the first genome into the second. In the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010), Pairwise Rearrangement is #P-complete (Bailey, et. al., COCOON 2023), which implies that exact sampling is intractable. In order to cope with this intractability, we investigate the parameterized complexity of this problem. We exhibit a fixed-parameter tractable algorithm with respect to the number of components in the adjacency graph that are not cycles of length 2 or paths of length 1. As a consequence, we obtain that Pairwise Rearrangement in the Single Cut-and-Join model is fixed-parameter tractable by distance. Our results suggest that the number of nontrivial components in the adjacency graph serves as the key obstacle for efficient sampling. 

We report our experiences implementing standards-based grading at scale in an Algorithms course, which serves as the terminal required CS Theory course in our department's undergraduate curriculum. The course had 200-400 students, taught by two instructors, eight graduate teaching assistants, and supported by two additional graders and several undergraduate course assistants. We highlight the role of standards-based grading (SBG) in supporting our students during the COVID-19 pandemic. We conclude by detailing the successes and adjustments we would make to the course structure.